package com.tuling.code.algorithm.sort;

public class QuickSort {

	public void display(int[] a) {
		int index = 0;
		for (int i : a) {
			if (index == a.length - 1) {
				System.out.print(i);
			} else {
				System.out.print(i + ",");
			}
			index++;
		}
		System.out.println("");
	}

	/**
	 * 
	 * @param arr
	 * @param low
	 * @param high
	 */
	public void quickSort(int[] a, int start, int end) {
		if (start < end) {
			int baseNum = a[start]; // 选基准值
			int midNum;
			int i = start;
			int j = end;
			do {
				while (a[i] < baseNum && i < end) {
					i++;
				}

				while (a[j] > baseNum && j > start) {
					j--;
				}

				if (i <= j) {
					midNum = a[i];
					a[i] = a[j];
					a[j] = midNum;
					i++;
					j--;
				}

			} while (i < j);

			if (start < j) {
				quickSort(a, start, j);
			}

			if (end > i) {
				quickSort(a, i, end);
			}
		}

		display(a);
	}

	private int partition(int[] a, int low, int high) {
		// 固定的切分方式
		int key = a[low];
		while (low < high) {
			while (a[high] >= key && high > low) { // 从后半部分向前扫描
				high--;
			}

			a[low] = a[high];

			while (a[low] <= key && high > low) { // 从前半部分向后扫描
				low++;
			}

			a[high] = a[low];
		}
		
		a[high] = key;
		return high;
	}
	
	public void sort(int[]a , int low , int high){
		if(low >= high){
			return ;
		}
		
		int index = partition(a, low, high);
		sort(a, low, index-1);
		sort(a, index+1, high);
		display(a);
	}

	public static void main(String[] args) {
		int[] a = { 1, 100, 2, 0, 9, 3, 12, 7, 8, -3, 4, 65, 22 };
		QuickSort qs = new QuickSort();
		//qs.quickSort(a, 0, a.length - 1);
		qs.sort(a, 0,a.length-1);
	}
}
